class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};



class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0, n = s.length();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = max(maxans, dp[i]);
            }
        }
        return maxans;
    }
};




class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<vector<int>> G(n + 1);
        for (int i = 0; i < edges.size(); ++i) {
            G[edges[i][0]].push_back(edges[i][1]);
            G[edges[i][1]].push_back(edges[i][0]);
        }
        vector<bool> visited(n + 1, false);
        return dfs(G, visited, 1, t, target);
    }

    double dfs(vector<vector<int>>& G, vector<bool>& visited, int i, int t, int target) {
        int nxt = i == 1 ? G[i].size() : G[i].size() - 1;
        if (t == 0 || nxt == 0) {
            return i == target ? 1.0 : 0.0;
        }
        visited[i] = true;
        double ans = 0.0;
        for (int j : G[i]) {
            if (!visited[j]) {
                ans += dfs(G, visited, j, t - 1, target);
            }
        }
        return ans / nxt;
    }
};





struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};


class Solution {
private:
    // 存储有向图
    vector<vector<int>> edges;
    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    vector<int> visited;
    // 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶
    vector<int> result;
    // 判断有向图中是否有环
    bool valid = true;

public:
    void dfs(int u) {
        // 将节点标记为「搜索中」
        visited[u] = 1;
        // 搜索其相邻节点
        // 只要发现有环，立刻停止搜索
        for (int v: edges[u]) {
            // 如果「未搜索」那么搜索相邻节点
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            // 如果「搜索中」说明找到了环
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        // 将节点标记为「已完成」
        visited[u] = 2;
        // 将节点入栈
        result.push_back(u);
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        if (!valid) {
            return {};
        }
        // 如果没有环，那么就有拓扑排序
        // 注意下标 0 为栈底，因此需要将数组反序输出
        reverse(result.begin(), result.end());
        return result;
    }
};




class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
};





#include<bits/stdc++.h> 

using namespace std;
const int N=2e5+7;
int n,dp[N],ans;
int main( )
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>dp[i];
    ans=dp[1];
    for(int i=2;i<=n;i++){
        if(dp[i-1]>=0)
            dp[i]=dp[i-1]+dp[i];
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

public:
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
};




#include<bits/stdc++.h> 
using namespace std;
const int N=2e5+7;
int a[N],b[N],c[N],n;
long long ans;
int lowbit(int x)
{
    return x&-x;
}
void add(int i,int x)
{
    for(;i<=n;i+=lowbit(i))
    {
        c[i]+=x;
    }
}
int sum(int i)
{
    int ans=0;
    for(;i>0;i-=lowbit(i))
        ans+=c[i];
    return ans;
}
bool cmp(const int x,const int y)
{
    if(b[x]==b[y])
        return x>y;
    return b[x]>b[y];
}
int main( )
{
    cin>>n;
    for( int i=1;i<=n;i++)
    {
        cin>>b[i];
        a[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        add(a[i],1);
        ans+=sum(a[i]-1);
    }
    cout<<ans<<endl;
    return 0;
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

#include<bits/stdc++.h> 
using namespace std;
const int mod = 1e5 + 3;
const int N = 1e5 + 3;
struct NODE {
    int val[6],next;
}insect [N];
int n,h[N],idx;

int F(int *a)
{
    long long sum = 0,pro = 1;
    for (int i=0;i<6;i++)
    {
        sum =(sum +a[i])%mod;
        pro = pro*a[i]% mod;
    }
    return (sum + pro) %mod;
}
bool equal(int *a,int *b)
{
    for (int i = 0; i<6; i++){
        for (int j =0;j<6;j++){
            bool flag = true;
            for (int k= 0; k<6;k++){
                if (a[(i +k)%6] !=b[(j +k)%6])
                flag = false;
            }
            if(flag)
                return true;
            flag = true;
            for (int k=0; k<6; k++){
                if (a[(i +k)%6] != b[(j -k +6)%6])
                flag = false;
            }
            if(flag)
                return true;
        }
    }
    return false;
}
bool find( int *a) {
    int k= F(a);
    for(int i = h[k]; i != -1; i = insect[i].next)
        if (equal(insect[i].val,a))
            return true;
        return false;
}
void insert(int *a){
    int k = F(a);
    memcpy(insect[idx].val,a,6* sizeof(int));
    insect[idx].next = h[k];
    h[k]= idx;
    idx++;
}


int main( )
{
    memset(h, -1,sizeof h);
    cin >> n;
    while (n--){
        int a[6];
        for (int i =0; i<6;i++)
        cin >> a[i];
        if(find(a))
        {
            cout << "found.";
            return 0;
        }
        else
            insert(a);
    }
    cout <<"No";

    return 0;
}


#include<bits/stdc++.h> 

using namespace std;
const int N=1e5+7;

int fa[N],t[N],n,m;
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void merge(int i,int j)
{
    int x=find(i),y=find(j);
    if(x!=y)
    {
        fa[x]=y;
        t[y]+=t[x];
    }
}
int main( )
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
        fa[i]=i;
    }
    while(m--)
    {
        int op,a,b;
        cin>>op;
        if(op==1)
        {
            cin>>a>>b;
            merge(a,b);
        }
        else
        {
            cin>>a;
            cout<<t[find(a)]<<endl;
        }
    }
    return 0;
}


//#include<bits/stdc++.h> 

using namespace std;
const int N=1e5+7;

int fa[N],t[N],n,m;
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void merge(int i,int j)
{
    int x=find(i),y=find(j);
    if(x!=y)
    {
        fa[x]=y;
        t[y]+=t[x];
    }
}
int main( )
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
        fa[i]=i;
    }
    while(m--)
    {
        int op,a,b;
        cin>>op;
        if(op==1)
        {
            cin>>a>>b;
            merge(a,b);
        }
        else
        {
            cin>>a;
            cout<<t[find(a)]<<endl;
        }
    }
    return 0;
}


class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> factors = {2, 3, 5};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;
        seen.insert(1L);
        heap.push(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.top();
            heap.pop();
            ugly = (int)curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (!seen.count(next)) {
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};



class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        auto levelOrder = vector<vector<int>>();
        if (!root) {
            return levelOrder;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto level = vector<int>();
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            levelOrder.push_back(level);
        }
        reverse(levelOrder.begin(), levelOrder.end());
        return levelOrder;
    }
};


//约瑟夫报数模拟
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, s=0;
    scanf("%d%d", &n, &m);
    for(int i=2;i<=n;i++)
        s = (s+m)%i;
    printf("%d\n", s+1);
    return 0;
}

//另类加法-位运算
class UnusualAdd {
public:
    int addAB(int A, int B) {
        while(B != 0){
            int a = A^B;
            int b = (A&B)<<1;
            A = a;
            B = b;
        }
        return A;
    }
};


//模拟-字符串大数相乘
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        string ans = "0";
        int m = num1.size(), n = num2.size();
        for (int i = n - 1; i >= 0; i--) {
            string curr;
            int add = 0;
            for (int j = n - 1; j > i; j--) {
                curr.push_back(0);
            }
            int y = num2.at(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.at(j) - '0';
                int product = x * y + add;
                curr.push_back(product % 10);
                add = product / 10;
            }
            while (add != 0) {
                curr.push_back(add % 10);
                add /= 10;
            }
            reverse(curr.begin(), curr.end());
            for (auto &c : curr) {
                c += '0';
            }
            ans = addStrings(ans, curr);
        }
        return ans;
    }

    string addStrings(string &num1, string &num2) {
        int i = num1.size() - 1, j = num2.size() - 1, add = 0;
        string ans;
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.at(i) - '0' : 0;
            int y = j >= 0 ? num2.at(j) - '0' : 0;
            int result = x + y + add;
            ans.push_back(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        reverse(ans.begin(), ans.end());
        for (auto &c: ans) {
            c += '0';
        }
        return ans;
    }
};



//前缀和
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        int max=-100000;
        for(int i=0;i<dp.size();i++)
        {
            if(i==0)
            dp[i]=nums[i];
            else if(nums[i]+dp[i-1]>nums[i])
            dp[i]=nums[i]+dp[i-1];
            else
            dp[i]=nums[i];
            if(dp[i]>max)  
            max=dp[i];
           // cout<<i<<dp[i][i]<<endl;
        }
        
        return max;
    }
};

//滑动窗口+哈希
class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};

//非欧几里得距离为2
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int main()
 {
	int W, H;
	int count=0;
	vector<vector<int> > grid(H,vector<int>(W,0));
	for(int i=0;i<H; i++){
	     for(int j=0; j<W; j++){
	            if((i-2>=0 && grid[i-2][j]) || (j-2>=0 && grid[i][j-2])) 
		grid[i][j]=0;
	            else {
		grid[i][j]=1;
		count++;
	            }
	}
               cout<< count<<endl;

}

//买卖股票 （动态规划/贪心）
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp0 = 0, dp1 = -prices[0];
        for (int i = 1; i < n; ++i) {
            int newDp0 = max(dp0, dp1 + prices[i]);
            int newDp1 = max(dp1, dp0 - prices[i]);
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return dp0;
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
};


//进制转换
#include<string>
#include <iostream>
using namespace std;
int main(){
    string s="",table="0123456789ABCDEF";
    int m,n;
    cin>>m>>n;
    if(m==0)
     cout<<m<<endl;
    while(m){
        if(m<0){
            m=-m;
            cout<<"-";
        }
        s=table[m%n]+s;
        m/=n;
    }
    cout<<s<<endl;
    return 0;
}
//移除重复节点
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        unordered_set<int> occurred = {head->val};
        ListNode* pos = head;
        // 枚举前驱节点
        while (pos->next != nullptr) {
            // 当前待删除节点
            ListNode* cur = pos->next;
            if (!occurred.count(cur->val)) {
                occurred.insert(cur->val);
                pos = pos->next;
            } else {
                pos->next = pos->next->next;
            }
        }
        pos->next = nullptr;
        return head;
    }
};


//滑动窗口
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum < x) {
            return -1;
        }

        int right = 0;
        int lsum = 0, rsum = sum;
        int ans = n + 1;

        for (int left = -1; left < n; ++left) {
            if (left != -1) {
                lsum += nums[left];
            }
            while (right < n && lsum + rsum > x) {
                rsum -= nums[right];
                ++right;
            }
            if (lsum + rsum == x) {
                ans = min(ans, (left + 1) + (n - right));
            }
        }

        return ans > n ? -1 : ans;
    }
};



//删除公共字符
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int hs[130]={0};
    string s1(1000,'\0');
    string s2(100,'\0');
    getline(cin,s1);
    getline(cin,s2);
    
    for(auto e:s2)
    {
        hs[e]=1;
    }
    for(auto e:s1)
    {
        if(hs[e]==1)
            continue;
        else
            cout<<e;
    }
    return 0;   
    
}

//原地归并排序链表
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode* prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr) {
                ListNode* head1 = curr;
                for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                    curr = curr->next;
                }
                ListNode* next = nullptr;
                if (curr != nullptr) {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};


//dp-通配符匹配
// class Solution {
// public:
//     bool isMatch(string s, string p) {
//         if(s.size()==0)
//         {
//             for(int i=0;i<p.size();i++)
//             {
//                 if(p[i]!='*')
//                     return 0;
//             }
//             return 1;
//         }
//         if(p.size()==0)
//             return 0;
//         vector<vector<int>> result(s.size());
//         for(int i=0;i<s.size();i++)
//         {
//             result[i].resize(p.size());
//             for(int j=0;j<p.size();j++)
//             {
//                 if(i==0&&j==0)
//                     result[i][j]=s[i]==p[j]||p[j]=='?'||p[j]=='*';
//                 else
//                 {
//                     if(p[j]=='?')
//                     {
//                         if(i>0&&j>0)
//                             result[i][j]=result[i-1][j-1];
//                          else if(i==0)
//                         {
//                             if(j==0)
//                                 result[i][j]=1;
//                             else
//                             {
//                                 result[i][j]=1;
//                                 int tmp=j-1;
//                                 while(tmp>=0)
//                                 {
//                                     if(p[tmp]!='*')
//                                     {
//                                         result[i][j]=0;
//                                         break;
//                                     }
//                                     tmp--;
//                                 }
//                             }
//                         }
//                         //j==0  i>0
//                         else
//                         {
//                             result[i][j]=0;
//                         }
//                     }   

                
        
//                     else if(p[j]=='*')
//                     {
//                         //任意result[i][j-1]为1则匹配  
//                         if(j==0)
//                             result[i][j]=1;
//                         else
//                         {
//                             result[i][j]=0;
//                             for(int ii=0;ii<=i;ii++)
//                             {
//                                 if(result[ii][j-1]==1)
//                                 {
//                                     result[i][j]=1;
//                                     break;
//                                 }
//                             }
//                         }
//                     }
//                     else
//                     {
//                         if(s[i]!=p[j])
//                             result[i][j]=0;
//                         else
//                         {
//                             if(i>0&&j>0)
//                             {
//                                 result[i][j]=result[i-1][j-1];
//                             }
//                             else if(i==0)
//                             {
//                                 if(j==0)
//                                     result[i][j]=1;
//                                 else
//                                 {
//                                     result[i][j]=1;
//                                     int tmp=j-1;
//                                     while(tmp>=0)
//                                     {
//                                         if(p[tmp]!='*')
//                                         {
//                                             result[i][j]=0;
//                                             break;
//                                         }
//                                         tmp--;
//                                     }
//                                 }
//                             }
//                             //j==0  i>0
//                             else
//                             {
//                                 result[i][j]=0;
//                             }
//                         }    
                        
//                     }
//                 }
//             }
//                 //cout<<i<<" "<<j<<" "<<result[i][j]<<endl;
//         }

//         return result[s.size()-1][p.size()-1];
//     }
// };

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[i - 1] == '*') {
                dp[0][i] = true;
            }
            else {
                break;
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
                }
                else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

//最大子序和
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};


//排序
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int i = 0; i < nums.size(); i++) {
            count[nums[i]]++;
        }
        vector<int> ans;
        for (auto &it: count) {
            if (it.second > nums.size() / 3)
                ans.push_back(it.first);
        }
        return ans;
    }
};

//铺地毯
#include"cstdio"
#include"iostream"
using namespace std;
int a[10010],b[10010],g[10010],k[10010],s[10010];//开数组，不多说，s数组标记地毯序号
int main()
{
 //ios::sync_with_stdio(false);//可关闭和stdio同步加速
 int n,i,x,y,ok=1;//ok标记是否有解
 cin>>n;
 for(i=1;i<=n;i++)   
 {cin>>a[i]>>b[i]>>g[i]>>k[i];   
  s[i]=i;//把i存进数组里  
 }   
 cin>>x>>y;
 for(i=n;i>=1;i--)
 {
  if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i])
  {
  ok=0;cout<<s[i];break;//逆序找，发现有解，把ok标记为0，输出并退出循环
  }                
 }
 if(ok) cout<<"-1";//如果找遍了都没解就输出-1
 return 0;   
}


/*dfs
#include <bits/stdc++.h>
using namespace std;

int n;
int a[1010];//正整数的值
int mi=1e9;
//判断是否为质数
bool primer(int x){
   for(int i=2;i*i<=x;i++){
       if(x%i==0){
           return false;
       }
   }
    return true;
}
void dfs(int x,set<int> s,int temp){
    if(x==n){
        mi=min(mi,temp);
        return;
    }
    for(int i=2;i<=a[x];i++){
        if(a[x]%i==0 && primer(i)&&!s.count(i)){
            s.insert(i);
            dfs(x+1,s,temp+i);
            s.erase(i);
        }
    }
}
int  main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    set<int> s;
    dfs(0,s,0);
    if(mi==1e9)cout<<-1;
    else cout<<mi;
    return 0;
    
}
*/

//动态规划-装箱问题
#include<iostream>
using namespace std;

int v, n;
int a[40];
int dp[20100];

int main() {
    cin >> v >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    dp[0] = 1;
    for(int i = 1;i <= n; i ++ ) {
        for(int j = v; j >= a[i]; j --) {
            dp[j] = dp[j] || dp[j - a[i]];
        }
    }
    for(int j = v;j >= 0;j --) {
        if(dp[j]) {
            cout << v - j;
            break;
        } 
    } 
} 

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;
int main()
{
	cout << "helloworld!" << endl;
	return 0;
}


// d1 - d2;
int Date::operator-(const Date& d) const
{
	Date max = *this;
	Date min = d;
	int flag = 1;

	if (*this < d)
	{
		max = d;
		min = *this;
		flag = -1;
	}

	int n = 0;
	while (min != max)
	{
		++min;
		++n;
	}

	return n*flag;
}

//void Date::operator<<(ostream& out)
//{
//	out << _year << "" << _month << "" << _day << "" << endl;
//}



//ostream& operator<<(ostream& out, const Date& d)
//{
//	out << d._year << "" << d._month << "" << d._day << "" << endl;
//	return out;
//}
//
//istream& operator>>(istream& in, Date& d)
//{
//	in >> d._year >> d._month >> d._day;
//	return in;
//}


